package com.atguigu.list;

import javafx.util.Pair;


//递归实现链表
public class LinkedListR<E> {

    private class Node{
        public E e;
        public Node next;
        public Node(E e,Node next){
            this.e=e;
            this.next=next;
        }
        public Node(E e){
            this(e,null);
        }
        public Node(){
            this(null,null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }
    private Node head;
    private int size;
    public LinkedListR(){
        head=null;
        size=0;
    }
    public int getSize(){
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }
    public void add(int index,E e){
        if(index<0||index>size){
            throw new IllegalArgumentException("Add failed index illegal!");
        }
        head=add(head,index,e);
    }
    //向链表第index位置添加元素
    private Node add(Node head,int index,E e){
        if(index==0){
            return new Node(e,head);
        }
        head.next=add(head.next,index-1,e);
        size++;
        return head;
    }
    public void addFirst(E e){
        add(0,e);
    }
    public void addLast(E e){
        add(size,e);
    }
    public E get(int index){
        if(index<0||index>=size){
            throw new IllegalArgumentException("get failed , index illegal!");
        }
        return get(head,index).e;
    }
    private Node get(Node head,int index){
        if(index==0){
            return head;
        }
        return get(head.next,index-1);
    }
    public E getFirst(){
        return get(0);
    }
    public E getLast(){
        return get(size-1);
    }
    public void set(int index,E e){
        if(index<0||index>=size){
            throw new IllegalArgumentException("set failed , index illegal!");
        }
        set(head,index,e);
    }
    private void set(Node head,int index,E e){
        if(index==0){
            head.e=e;
            return ;
        }
        set(head.next,index-1,e);
    }
    public boolean contains(E e){
        return contains(head,e);
    }
    private boolean contains(Node head,E e){
        if(head==null){
            return false;
        }
        if(head.e.equals(e)){
            return true;
        }
        return contains(head.next,e);
    }
    public E remove(int index){
        if(index<0||index>=size){
            throw new IllegalArgumentException("remove failed , index illegal!");
        }
        Pair<Node,E>pair=remove(head,index);
        size--;
        head=pair.getKey();
        return pair.getValue();
    }
    private Pair<Node,E>remove(Node head,int index){
        if(index==0){
            return new Pair<Node,E>(head.next,head.e);
        }
        Pair<Node,E>res=remove(head.next,index-1);
        head.next=res.getKey();
        return new Pair<Node,E>(head,res.getValue());
    }
    public E removeFirst(){
        return remove(0);
    }
    public E removeLast(){
        return remove(size-1);
    }
    public void removeElement(E e){
        removeElement(head,e);
    }
    private Node removeElement(Node head,E e){
        if(head==null){
            return null;
        }
        if(head.e.equals(e)){
            size--;
            return head.next;
        }
        head.next=removeElement(head.next,e);
        return head;
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();

        Node cur = head;
        while(cur != null){
            res.append(cur).append("->");
            cur = cur.next;
        }
        res.append("NULL");

        return res.toString();
    }
}
